﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Interpreter
{
	internal class MapImpl
	{
		public int Capacity;
		public int Size;
		public Bucket[] Buckets;

		public MapImpl(int startingItemCount)
		{
			this.Capacity = startingItemCount < 10 ? 10 : startingItemCount * 7 / 5;
			this.Buckets = new Bucket[this.Capacity];
			this.Size = 0;
		}



		private const int OPTION_KEY = 1;
		private const int OPTION_VALUE = 2;
		private const int OPTION_PAIR = 3;

		private Value BuildItemList(int type)
		{
			Value[] output = new Value[this.Size];
			int n = 0;
			Bucket b;
			for (int i = this.Buckets.Length - 1; i >= 0; --i)
			{
				for (b = this.Buckets[i]; b != null; b = b.Next)
				{
					if (type == OPTION_KEY)
					{
						output[n++] = b.Key;
					}
					else if (type == OPTION_VALUE)
					{
						output[n++] = b.Value;
					}
					else
					{
						output[n++] = new Value(Value.TYPE_LIST, new Value[] { b.Key, b.Value }, 2);
					}
				}
			}

			return new Value(Value.TYPE_LIST, output, output.Length);
		}

		public Value BuildKeyList() { return this.BuildItemList(OPTION_KEY); }

		public Value BuildValueList() { return this.BuildItemList(OPTION_VALUE); }

		public Value BuildKeyValuePairList() { return this.BuildItemList(OPTION_PAIR); }

		public void Clear()
		{
			for (int i = this.Buckets.Length - 1; i >= 0; --i)
			{
				this.Buckets[i] = null;
			}

			this.Size = 0;
		}

		// returns true if there was a collision and overwite is not allowed
		public bool TryAdd(Value key, Value value, bool overwrite)
		{
			int hash = key.ValueHash();
			Bucket existing = Get(key, hash);
			if (existing != null)
			{
				if (overwrite)
				{
					existing.Key = key;
					existing.Value = value;
				}
				else
				{
					return true;
				}
			}
			else
			{
				int index = hash % this.Capacity;
				this.Buckets[index] = new Bucket(key, value, this.Buckets[index], hash);
				++this.Size;

				if (this.Size > this.Capacity)
				{
					this.Rehash();
				}
			}

			return false;
		}

		private void Rehash()
		{
			int bucketLength = this.Size * 2 + 1;
			int index;
			Bucket bNext;
			Bucket[] newBuckets = new Bucket[bucketLength];
			for (int i = 0; i < this.Buckets.Length; ++i)
			{
				for (Bucket b = this.Buckets[i]; b != null; b = bNext)
				{
					bNext = b.Next;
					index = b.Key.ValueHash() % bucketLength;
					b.Next = newBuckets[index];
					newBuckets[index] = b;
				}
			}
			this.Buckets = newBuckets;
			this.Capacity = bucketLength;
		}

		// We return the bucket for the benefit of wrapped references so a lookup doesn't need to occur twice.
		public Bucket Get(Value key, int hash)
		{
			Bucket bucket = this.Buckets[hash % this.Capacity];
			while (bucket != null)
			{
				if (bucket.Key.Type == key.Type)
				{
					switch (key.Type)
					{
						case Value.TYPE_NULL:
						case Value.TYPE_BOOLEAN:
							if (key == bucket.Key)
							{
								return bucket;
							}
							break;

						case Value.TYPE_STRING:
							if (key.Value0.Equals(bucket.Key.Value0))
							{
								return bucket;
							}
							break;

						case Value.TYPE_INTEGER:
						case Value.TYPE_FLOAT:
						case Value.TYPE_LIST:
						case Value.TYPE_MAP:
						case Value.TYPE_CLASS:
							if (key.Value0 == bucket.Key.Value0)
							{
								return bucket;
							}
							break;

						case Value.TYPE_INSTANCE:
							// TODO: some notion of a pointer. I'd like to keep this implementation the same as on JavaScript
							throw new NotImplementedException("Keying off class instances is not implemented yet.");
					}
				}

				bucket = bucket.Next;
			}

			// a hard null means not found. Not to be confused with Value.Null
			return null;
		}
	}

	internal class Bucket
	{
		public Bucket(Value key, Value value, Bucket next, int hash)
		{
			this.Key = key;
			this.Value = value;
			this.Next = next;
			this.Hash = hash;
		}
		public Value Value;
		public Value Key;
		public Bucket Next;
		public int Hash;
	}
}
